package com.example.demo.leetcode.top;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 根据一棵树的前序遍历与中序遍历构造二叉树。
 *
 * 注意:
 * 你可以假设树中没有重复的元素。
 *
 * 例如，给出
 *
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 **/
public class Btree_从前序中序遍历出二叉树 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0 || inorder.length==0){
            return null;
        }
        //拿到根节点
        TreeNode root = new TreeNode(preorder[0]);
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==root.val){
                //找到中序便利数组中的子节点，对先序遍历数组，中序便利数组进行拆分
                //先序遍历 左子树+根节点的长度 = 中序便利 左子树+根节点长度
                int [] pre_left= Arrays.copyOfRange(preorder,1,i+1);//i+1防止数组越界，1,0
                int [] pre_right=Arrays.copyOfRange(preorder,i+1,preorder.length); //i+1取右子树根节点
                //中序遍历完全分隔，所以取 [0,i],[i+1,inorder.length]; 第i个被取出来了
                int [] order_left= Arrays.copyOfRange(inorder,0,i+1);
                int [] order_right= Arrays.copyOfRange(inorder,i+1,inorder.length);
                root.left=buildTree(pre_left,order_left);
                root.right=buildTree(pre_right,order_right);
                break;
            }
        }
        return root;
    }


    public static void main(String[] args) {
        String [] arr ={"1","2","3"};
        String [] order_right= Arrays.copyOfRange(arr,0,3);
        for(String temp : order_right){
            System.out.println(temp);
        }
    }


 public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }



}
